package zuo.algo.util;

import zuo.algo.data.Node;
import zuo.algo.data.TreeNode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class TreeUtils {

    public static TreeNode getTree() {
        Map<Integer, TreeNode> map = new HashMap<>();
        return getTree(map);
    }

    public static TreeNode getTree(Map<Integer, TreeNode> map) {
        TreeNode root = new TreeNode(10);
        map.put(10, root);
        TreeNode node = new TreeNode(6);
        node.parent = map.get(10);
        root.left = node;
        map.put(6, node);
        node = new TreeNode(16);
        node.parent = map.get(10);
        root.right = node;
        map.put(16, node);
        node = new TreeNode(4);
        node.parent = map.get(6);
        root.left.left = node;
        map.put(4, node);
        node = new TreeNode(8);
        node.parent = map.get(6);
        root.left.right = node;
        map.put(8, node);
        node = new TreeNode(14);
        node.parent = map.get(16);
        root.right.left = node;
        map.put(14, node);
        node = new TreeNode(18);
        node.parent = map.get(16);
        root.right.right = node;
        map.put(18, node);
        node = new TreeNode(20);
        node.parent = map.get(18);
        root.right.right.right = node;
        map.put(20, node);
        return root;
    }

    public static <T extends Comparable<T>> void printTree(Node<T> root) {
        LinkedList<Node<T>> queue = new LinkedList<>();
        queue.add(root);
        Node<T> levelEnd = root;

        while (!queue.isEmpty()) {
            Node<T> node = queue.poll();
            System.out.print(node.value + " ");
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
            if (node == levelEnd) {
                System.out.println();
                levelEnd = queue.peekLast();
            }
        }
        System.out.println();
    }

    public static <T extends Comparable<T>> boolean isBalance(Node<T> node) {
        if (node == null) {
            return true;
        }
        boolean leftBalance = isBalance(node.left);
        int leftHeight = node.left == null ? 0 : node.left.n;
        boolean rightBalance = isBalance(node.right);
        int rightHeight = node.right == null ? 0 : node.right.n;
        return leftBalance && rightBalance && Math.abs(leftHeight - rightHeight) <= 1;
    }
}
